package _0_4_买卖股票

/**
原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

188. 买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。


示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

思路:
买卖股票 Ⅲ  只能买卖两次股票的递推公式
		dp[i][0] = dp[i-1][0]
第一次:	dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
		dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
第二次:  dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
		dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
		...
		第k次买卖

可得, 买卖两次股票, dp数组长度已经达到4了,
因为有一次买卖, 就会有一次买入动作, 一次卖出动作

本题dp数组即可定义为 dp[i][2k+1]   多出来的1是状态0不进行任何操作的情况
由于每次买和卖是两次动作, 所以j需要跳跃2
*/
// 分割等和子集 动态规划
// 时间复杂度O(n^2) 空间复杂度O(n)
// 买卖股票的最佳时机IV 动态规划
// 时间复杂度O(kn) 空间复杂度O(kn)
func maxProfit188(k int, prices []int) int {

	n := len(prices)
	if k == 0 || n == 0 {
		return 0
	} //买卖次数k=0 或者 数组长度为0, 直接返回0即可

	dp := make([][]int, n) //初始化数组
	for i := range dp {
		dp[i] = make([]int, 2*k+1)
	}

	//将第0天, j次买卖所持有的现金进行初始化   买的动作都初始化为-prices[0],卖是因为将当前的股票又卖出了,所持现金为0
	for j := 1; j < 2*k; j += 2 {
		dp[0][j] = -prices[0]
	}

	//从第1天开始,填充数组
	for i := 1; i < n; i++ {
		for j := 0; j < 2*k; j += 2 { //每天都有两种状态, 持有或不持有
			dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])
			dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])
		}
	}

	return dp[n-1][2*k] //返回第i天, 不持有股票状态的现金数
}
